package _0733_Flood_Fill;

import _0000_study._common.Output;

/**
 * Date: 2021/9/13 9:44
 * Content:
 * 执行用时：1 ms, 在所有 Java 提交中击败了66.25%的用户
 * 内存消耗：39.2 MB, 在所有 Java 提交中击败了74.22%的用户
 */
public class Solution {

    int[][] g;
    int n, m;
    boolean[][] st;
    static int[] dx = new int[]{-1, 0, 1, 0}, dy = new int[]{0, 1, 0, -1};

    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        g = image;
        n = g.length;
        m = g[0].length;
        st = new boolean[n][m];
        dfs(sr, sc);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (st[i][j])
                    g[i][j] = newColor;
        return g;
    }

    private void dfs(int x, int y) {
        st[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int a = x + dx[i], b = y + dy[i];
            if (a < 0 || a >= n || b < 0 || b >= m) continue;
            if (st[a][b]) continue;
            if (g[a][b] != g[x][y]) continue;
            dfs(a, b);
        }
    }

    public static void main(String[] args) {

        int[][] image = {
                {1, 1, 1},
                {1, 1, 0},
                {1, 0, 1},
        };
        Output.OutputBasicArray2D((new Solution()).floodFill(image, 1, 1, 2));
    }
}
